1. Field of the Invention
The present invention relates in general to database access techniques. In particular, aspects of the invention relate to fileservers which support caching and to methods and apparatus for ensuring cache consistency.
2. Related Art
In today's information age, the ability to access rapidly data which is held in databases is of utmost importance to companies and organisations whose business may rely on the data.
The speed with which remote equipment, or a client, is able to access data on a database relies on two major factors. The first factor is the speed with which a database fileserver can read data typically from a co-located external storage device such as a hard disk drive. This factor relies on the speed of the central processing unit (CPU) and on the disk access speed of the fileserver. The second factor is the capacity, or the bandwidth, of the communications link between the client and the fileserver.
A third factor effecting database access speed, which is extremely significant to the performance of an overall system, is the loading on the system. The loading is typically proportional to the number of clients which require database access. Both the number of operations performed by the CPU and the volume of data which needs to be transmitted across communications links increases as more clients require database access. Obviously, there is a point where the demands placed on the fileserver and communications links exceed optimum capability, at which point system performance will degrade.
System performance can be improved by increasing the speed of the fileserver and the bandwidth of the communications links. However, the related costs cannot always be justified. Also, there is always a limit to the speed at which current technologies can operate.
Another way of achieving better system performance, by reducing the database CPU and communications link loading, is by using cached copies of the data. The cached copies are typically located physically nearer to the clients, or even on the client systems themselves. Indeed, this technique has been widely adopted on the Internet by using Internet fileservers containing cached copies of data located at ‘mirror sites’. For example, master data accessible from a master Internet fileserver at a site in the USA might be copied, or cached, to a fileserver at a mirror site in the UK, from where a majority of European users might prefer to read the data. Thus, the data transfer overhead for transatlantic links and the demands placed on the master Internet fileserver are reduced, and the overall, perceived Internet performance is improved. In particular, the European users would expect to obtain far better data access performance by accessing the UK mirror site.
The use of cached data does raise important issues concerning data consistency. That is to say, it is sometimes difficult to know whether cached data is the same as the original, master data: the master data may change in some way after the cached copy is generated. In the case of the Internet, for example, at present a lack of consistency between master data and cached data may not be of great significance and, if it is significant, it is usually possible to choose to retrieve the master data, albeit at a slower rate, from the master database.
Cache consistency, or coherency, is however extremely important in commercial environments where the data, whether cached or master, forms the basis for making business decisions. Inconsistent data, or data which takes too long to access, inevitably results in reduced revenue. A simple example of such an environment is one for making flight bookings, where, for example, the master flight data is held in a database in the UK and travel agencies around Europe book seats on flights on the basis of cached data. In this example, under most circumstances, it is essential that the cached data is consistent with the master data.
Similar considerations are important in general in multiple-user systems, for example based on client/server or distributed database, networked environments, in which the users wherever possible rely on cached data to minimise CPU, data access, data transfer overheads imposed on master database fileservers, and overall network traffic.
In, for example, a client/server environment having multiple clients accessing a single, master database fileserver, there is typically considerable opportunity to maintain with each client a large cache of recently read data. A cache may be used during an active transaction to avoid the need to re-read data from the master database. However, if data is cached on a client and the client needs to re-access that data at a later time, unless the data in the master database cannot change, it must be assumed that the data on the cache is inconsistent, because there is no way of knowing differently. Thus, further master database access is needed to at least compare the current state of the data in the master database with the data in the cache database.
A decision whether or not to use data cacheing typically depends on the type of data to be accessed. Three common categories of data are described below.
Static data, that is data which rarely changes, are prime candidates for holding in a client cache database: the data can always be assumed to be current. However, usually a task must provided to ensure that changes to the static data are propagated to all client caches. This is typically done using an overnight batch process. For static data, there is no need for a real-time process to maintain consistency.
Highly dynamic data is extremely difficult to maintain in a consistent state. The basic reason is that if the data changes very often, the network and processor impact, in a client/server environment, of updating many client caches can be considerable. In some cases, the cost in terms of processing overhead and network bandwidth of maintaining the caches might exceed the cost of each client accessing the master database directly each time data is required. Thus, this category of data would typically not be cached.
In between static and highly dynamic data is a type of data which is not static, but which changes relatively infrequently compared with highly dynamic data. Typically, in this case, data might only be cached onto a client cache database, for example at a travel agency, during the period of an aircraft flight enquiry and seat booking operation. Then, there would be a high degree of certainty that the data remains consistent during the operation. However, there would never be total certainty because, coincidentally, another client, or travel agency, might book the only remaining seats on the respective flight between the times on which the first client started and completed its operation.
The simplest way to prevent data inconsistency, in for example the flight booking operation described above, would be to ‘lock’ any data on the master database which is being accessed by one client, thus making that data inaccessible, or at least only readable, to other clients for the whole period of the operation. This is called ‘pessimistic locking’. Typically, a lock table, which holds the identities of locked data which cannot be accessed or written to, is generated by the master fileserver. Such a system requires that all access requests made by clients invoke a lock table search on the fileserver before data access or writing is allowed, or denied.
Obviously, however, in an environment where the same data might need to be accessed or up-dated by several clients, for example for flight-booking purposes, pessimistic locking represents an unworkable solution with intolerable locking overheads.
Another method for dealing with possible inconsistency between cached and master data is discussed in the book “Transaction Processing—Concepts and Techniques” by Gray J and Reuter A, published by Morgan Kaufmann 1993, on pages 434 to 435. The method involves ‘optimistic locking’.
Optimistic locking allows clients connected to a fileserver to use cached data at any time for reading purposes, but as soon as a transaction is initiated, for example making a flight seat booking, the cached data is compared with the master data to ensure data consistency and the master data is locked only for the period of the actual transaction (in this example, the transaction is the actual database access and write procedure). This prevents another client from changing the master data during the transaction. If, after the transaction has been initiated, the data in the cache database is found to be inconsistent with the corresponding data in the master database, the cache database is updated with the latest master data, and the client is notified and left to resolve any problems the inconsistency might have caused.
The advantage of optimistic locking is that the master data is only locked for a very short period of time, for maybe less than one second, to carry out the actual transaction. In contrast, pessimistic locking requires the data accessed to be locked for the whole period of an operation, for example for the whole period of an enquiry and a transaction, which might take many minutes.
Although optimistic locking may therefore require extra processing by both a client and a fileserver, it can be seen that the technique is far better suited for dealing with relatively dynamic data which may need to be accessed by multiple clients.
When implementing optimistic locking, it is known sometimes to use time stamping to mark data rows in the master database with the time the data was last updated. In this way, if the time-stamp for a particular row of data held in a cache is the same as the row in the master database, the fileserver accepts that the cached data is current and there is no need to re-send the data row in question across the network to the client. Thus, network bandwidth is conserved whenever a cached copy is found to be current.